package hashmap;

import java.util.TreeMap;

/**
 * @program: play-structure
 * @author: baichen
 * 实现HashMap，这里的key不用具备可比性,key必须实现hashCode方法，Object已经实现，所以这里不用实现
 * 链地址法,不一定通过链表实现，也可以通过TreeMap
 **/
public class HashTable<K, V> {
    //保证时间复杂度变为 O(1)
    private static final int upperTol = 10;        //上限
    private static final int lowerTol = 2;        //下限
    private static final int initCapacity = 7;    //初始哈希表容量
    //TreeMap是基于红黑树实现的，哈希表可以看作是TreeMap
    private TreeMap<K, V>[] hashTable;
    private int M;  //选择合适的素数，做模使用
    private int size;   //哈希表存储的元素个数

    public HashTable(int M) {
        this.M = M;
        size = 0;
        hashTable = new TreeMap[M];   //开辟数组空间
        for (int i = 0; i < M; i++) {
            hashTable[i] = new TreeMap<>();
        }
    }

    public HashTable() {
        this(initCapacity);
    }

    private int hash(K key) {
        //这里与0x7fffffff，是为了消除key的符号，整型的最高位是符号位，1表示负数，0表示正数
        return (key.hashCode() & 0x7fffffff) % M;   //哈希表对应的索引
    }

    public int getSize() {
        return size;
    }

    public void add(K key, V value) {
        //避免多次计算hash值
        TreeMap<K, V> map = hashTable[hash(key)];
        if (map.containsKey(key))
            map.put(key, value);
        else {
            map.put(key, value);
            size++;
            //扩容
            if (size >= upperTol * M) { //即 N/M >= upperTol，避免除法出现浮点类型
                resize(2 * M);
            }
        }
    }

    public V remove(K key) {
        TreeMap<K, V> map = hashTable[hash(key)];
        V ret = null;
        if (map.containsKey(key)) {
            ret = map.remove(key);
            size--;
        }
        //缩容
        if (size < lowerTol * M && M / 2 >= initCapacity) {
            resize(M / 2);
        }
        return ret;
    }

    public void set(K key, V value) {
        TreeMap<K, V> map = hashTable[hash(key)];
        if (!map.containsKey(key)) {
            //key不存在
            throw new IllegalArgumentException(key + "doesn't exist!");
        }
        //修改值
        map.put(key, value);
    }

    public boolean contains(K key) {
        return hashTable[hash(key)].containsKey(key);
    }

    public V get(K key) {
        return hashTable[hash(key)].get(key);
    }

    private void resize(int newM) {
        TreeMap<K, V>[] newHashTable = new TreeMap[newM];
        for (int i = 0; i < newM; i++) {
            newHashTable[i] = new TreeMap<>();
        }
        int oldM = M;
        this.M = newM;    //注意更新M,因为hash函数中会对M取模
        for (int i = 0; i < oldM; i++) {
            TreeMap<K, V> map = hashTable[i];
            for (K key : map.keySet())
                newHashTable[hash(key)].put(key, map.get(key));
        }
        this.hashTable = newHashTable;
    }
}
